import collections
from typing import List

MAX_INT = 241


class Solution:
    def shortestSuperstring(self, words: List[str]) -> str:
        size = len(words)

        # ---------- 移除所有被其他词完全包含的单词 ----------
        # 找出所有被完全包含的单词
        include_word_idx = set()
        for i in range(size):
            for j in range(size):
                if i != j and words[i] in words[j]:
                    include_word_idx.add(i)

        # 移除被完全包含的单词
        words = [words[i] for i in range(size) if i not in include_word_idx]
        size = len(words)

        print("没有被完全包含的单词:", words)

        # ---------- 构造各个单词连接之间可复用的字母数量的有向图 ----------
        # 定义有向图：graph[i][j] = 在第i个单词后放置第j个单词，可复用的字母数量
        graph = [[0] * size for _ in range(size)]

        # 构造有向图
        for i in range(size):
            for j in range(size):
                if i != j:
                    # 计算两个单词的最大可复用的字母数量
                    for k in range(1, min(len(words[i]), len(words[j]))):
                        if words[i][-k:] == words[j][:k]:
                            graph[i][j] = k

        # 计算每个顶点的值
        values = [len(words[i]) for i in range(size)]

        # ---------- 基于广度优先搜索的动态规划寻找最短路径 ----------
        # 定义状态矩阵：dp[i][j] = 当前位于顶点i，已遍历顶点情况为j的最短路径
        dp = [[""] * pow(2, size) for _ in range(size)]

        # 定义广度优先搜索的当前结点队列
        queue = collections.deque()

        # 添加从各个顶点出发的情况
        for i in range(size):
            stat = (1 << i)
            queue.append((i, stat))
            dp[i][stat] = words[i]

        # 广度优先搜索转移状态
        while queue:
            i0, stat0 = queue.popleft()
            v0 = dp[i0][stat0]
            for i1 in range(size):
                if not stat0 & (1 << i1):
                    stat1 = stat0 | (1 << i1)
                    v1 = v0 + words[i1][graph[i0][i1]:]
                    if dp[i1][stat1] == "" or len(v1) < len(dp[i1][stat1]):
                        dp[i1][stat1] = v1
                        queue.append((i1, stat1))

        return min([dp[i][pow(2, size) - 1] for i in range(size)], key=lambda x: len(x))


if __name__ == "__main__":
    # alexlovesleetcode
    print(Solution().shortestSuperstring(["alex", "loves", "leetcode"]))

    # gctaagttcatgcatc
    print(Solution().shortestSuperstring(["catg", "ctaagt", "gcta", "ttca", "atgcatc"]))
